This invention relates to the field of computer systems. More particularly, a programmable finite state machine is provided, along with methods of using the state machine to facilitate the hardware processing of an XML document or other structured stream of data.
The availability of distributed computing resources and high-bandwidth interconnections (e.g., the Internet) has enabled tremendous growth in the serving and sharing of applications and data across a distributed computing environment such as the Internet or an intranet. In particular, web services and service-oriented architectures continue to grow in popularity.
XML (eXtensible Markup Language), developed by the World Wide Web Consortium (W3C), provides a class of data objects (i.e., XML documents) for conveying data. XML is increasingly chosen as the way to transfer and store data within a service-oriented architecture or distributed computing environment, partly because it provides a well-defined format supported on virtually all computer platforms and architectures. Of particular note, the web services infrastructure is being built around XML.
An XML document consists of a series of characters, some of which form character data and some of which form markup. Markup encodes a description of the document's layout and structure, and includes comments, tags or delimiters (e.g., start tags, end tags, white space), declarations (e.g., document type declarations, XML declarations, text declarations), processing instructions and so on. Character data comprises all document text that is not markup.
Because an XML document is textual in nature, a software application that consumes the document's data must be able to examine the document, access its structure and content (e.g., to separate character data from markup) and place the data into an internally usable form. A software module that parses an XML document is generally called an XML processor, and works on behalf of the application. Applications often contain their own XML processors, thus causing duplication of effort among multiple applications.
A large proportion of the processor time needed to execute program instructions for parsing an XML document (e.g., approximately 50-70%) is spent decoding and validating the document's characters, tokenizing its content, and creating and maintaining a symbol table for the tokenization. Even though these tasks must be performed in similar manners for many XML documents, they continue to be done in software in almost all computing environments.
Additional processing is required if a security scheme must be applied to accept or examine an incoming secure XML document, or to make an outgoing XML document secure. The amount of additional processing increases with the complexity of the security mechanism (e.g., the size of a cryptographic key used to decrypt or encrypt the document, the type of digital signature). Thus, the nature of software already slows the processing of XML documents; the additional processing required to enforce a security scheme makes the situation even worse.
Because parsing of XML documents has always been performed in software, the increasing use of XML documents may cause an XML processor to become a bottleneck and consume more and more processor time—time that could otherwise be spent executing the application or performing other work. The demand for processor time required for software parsing of XML documents will only increase as more and more organizations and applications adopt XML as a means for transferring data.
And, because virtually all XML documents must be parsed before their data can be manipulated, XML parsing is critical to related technologies such as XSLT (Extensible Stylesheet Language Transformations), Xpath (XML Path Language), UBL (Universal Business Language), etc.
Attempts to provide superior XML processing solutions fail to achieve this goal for various reasons. For example, some proposed hardware solutions involve devices located across a PCI-X (Peripheral Component Interconnect—eXtended) bus or other communication bus from a host computer system's central processing unit (CPU). These proposed solutions suffer from excessive memory and communication (e.g., bus, network) latencies, thereby limiting their efficiency. And, some solutions may lack the necessary resources (e.g., dedicated processor, memory, security engine) for expediting the processing of XML documents.
Other devices are implemented as separate network nodes, such as appliances based on standard server hardware, and appear to simply involve traditional software methods of XML processing. Dedicating a network device (e.g., an appliance) to software-based XML processing does little to expedite the handling of XML documents.
One problem with software-based efforts to process XML documents is that they require a large number of inefficient string comparisons. For example, each time a piece of a document is read by an application or XML processor, it is serially compared to a number of XML entity forms (e.g., tags, declarations, comments) to determine the significance of that document piece. This can take a noticeable amount of time for a long document.
Another problem with existing XML processors is that they are designed to process an entire XML document before moving to the next. A very large document may therefore monopolize the XML processor, to the detriment of smaller documents.
A finite state machine (FSM) is an abstract machine for modeling the behavior of application programs, and is composed of states, transitions and actions. A state stores historical information about the application, in that it reflects program input up to the present moment.
Each state of a finite state machine has transitions to any number of other states. A transition thus indicates a state change, and is described by a condition (or input) that must occur in order to enable the transition. As a result of a transition, a new state is entered (or the same state is re-entered) and some action (or output) may result. A state machine may alternatively be viewed as a function that maps a sequence of input events into a corresponding sequence of output events.
In some situations, an FSM may be a better tool than structured program code for solving a programming task. For example, a text string representing a floating point number may comprise a sequence of characters very similar to an algebraic expression. To distinguish one from the other, a procedural set of rules might be applied that defines the format of a text string or an expression. If implemented using structured program code, a lengthy series of IFS, ELSES and/or other statements must be traversed to perform the analysis. An FSM may be written to perform the same task, using notation that is easier to understand.
Programmable finite state machines having large numbers of states and state transitions traditionally have not been implemented in hardware, due to the inherent cost and complexity.